Scramble String/ Distinct Subsequences

发表于

Scramble String

Question

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

1
2
3
4
5
6
7
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

Analysis

LeetCode Discuss

验证两个串是否为Scramble的方式即判断他们是否具有相同的字母数，由此递归的划分字符串进行判断

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1.length()!=s2.length())    return false;
        if(s1.equals(s2))   return true;
        int[] cnt=new int[26];
        for(int i=0;i<s1.length();i++){
            cnt[s1.charAt(i)-'a']++;
            cnt[s2.charAt(i)-'a']--;
        }
        for(int tmp:cnt){
            if(tmp!=0)
                return false;
        }
        for(int i=1;i<s1.length();i++){
            if(isScramble(s1.substring(0,i),s2.substring(0,i))&&isScramble(s1.substring(i),s2.substring(i))) return true;
            if(isScramble(s1.substring(0,i),s2.substring(s2.length()-i))&&isScramble(s1.substring(i),s2.substring(0,s2.length()-i))) return true;
        }
        return false;
    }
}